% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (C) 1999  Allen B. Downey

% This LaTeX source is free software; you can redistribute it and/or
% modify it under the terms of the GNU General Public License as
% published by the Free Software Foundation (version 2).

% This LaTeX source is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
% General Public License for more details.

% Compiling this LaTeX source has the effect of generating
% a device-independent representation of a textbook, which
% can be converted to other formats and printed.  All intermediate
% representations (including DVI and Postscript), and all printed
% copies of the textbook are also covered by the GNU General
% Public License.

% This distribution includes a file named COPYING that contains the text
% of the GNU General Public License.  If it is missing, you can obtain
% it from www.gnu.org or by writing to the Free Software Foundation,
% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.


\chapter{Fruitful functions}

\section{Return values}
\index{return}
\index{statement!return}
\index{function!fruitful}
\index{fruitful function}
\index{return value}
\index{void}
\index{function!void}

Some of the built-in functions we have used, like the math
functions, have produced results.  That is, the effect of
calling the function is to generate a new value, which we
usually assign to a variable or use as part of an expression.
For example:

\index{math function!exp}
\index{math function!sin}

\begin{verbatim}
  double e = exp (1.0);
  double height = radius * sin (angle);
\end{verbatim}
%
But so far all the functions we have written have been {\bf void}
functions; that is, functions that return no value.  When you call
a void function, it is typically on a line by itself, with
no assignment:

\begin{verbatim}
  nLines (3);
  countdown (n-1);
\end{verbatim}
%
In this chapter, we are going to write functions that return things,
which I will refer to as {\bf fruitful} functions, for want of a
better name.  The first example is {\tt area}, which takes a {\tt
double} as a parameter, and returns the area of a circle with the
given radius:

\index{math function!acos}
\index{pi}

\begin{verbatim}
double area (double radius) {
  double pi = acos (-1.0);
  double area = pi * radius * radius;
  return area;
}
\end{verbatim}
%
The first thing you should notice is that the beginning of the
function definition is different.  Instead of {\tt void}, which
indicates a void function, we see {\tt double}, which indicates that
the return value from this function will have type {\tt double}.

Also, notice that the last line is an alternate form of the
{\tt return} statement that includes a return value.  This
statement means, ``return immediately from this function and
use the following expression as a return value.''  The
expression you provide can be arbitrarily complicated,
so we could have written this function more concisely:

\begin{verbatim}
double area (double radius) {
  return acos(-1.0) * radius * radius;
}
\end{verbatim}
%
On the other hand, {\bf temporary} variables like {\tt area} often
make debugging easier.  In either case, the type of the expression in
the {\tt return} statement must match the return type of the function.
In other words, when you declare that the return type is {\tt double},
you are making a promise that this function will eventually
produce a {\tt double}.  If you try to {\tt return} with no
expression, or an expression with the wrong type, the compiler will
take you to task.

\index{temporary variable}
\index{variable!temporary}

Sometimes it is useful to have multiple return
statements, one in each branch of a conditional:

\begin{verbatim}
double absoluteValue (double x) {
  if (x < 0) {
    return -x;
  } else {
    return x;
  }
}
\end{verbatim}
%
Since these returns statements are in an alternative conditional, only
one will be executed.  Although it is legal to have more than one
{\tt return} statement in a function, you should keep in mind that as soon
as one is executed, the function terminates without executing any
subsequent statements.

Code that appears after a {\tt return} statement, or any place else
where it can never be executed, is called {\bf dead code}.  Some
compilers warn you if part of your code is dead.

\index{dead code}

If you put return statements inside a conditional, then
you have to guarantee that {\em every possible path} through
the program hits a return statement.  For example:

\begin{verbatim}
double absoluteValue (double x) {
  if (x < 0) {
    return -x;
  } else if (x > 0) {
    return x;
  }                          // WRONG!!
}
\end{verbatim}
%
This program is not correct because if {\tt x} happens to be 0, then
neither condition will be true and the function will end without hitting
a return statement.  Unfortunately, many C++ compilers do not catch
this error.  As a result, the program may compile and run, but the
return value when {\tt x==0} could be anything, and will probably
be different in different environments.

\index{absolute value}
\index{error!compile-time}
\index{compile-time error}

By now you are probably sick of seeing compiler errors, but as you
gain more experience, you will realize that the only thing worse
than getting a compiler error is {\em not} getting a compiler error
when your program is wrong.

Here's the kind of thing that's likely to happen: you test {\tt
absoluteValue} with several values of {\tt x} and it seems to work
correctly.  Then you give your program to someone else and they run it
in another environment.  It fails in some mysterious way, and it
takes days of debugging to discover that the problem is an
incorrect implementation of {\tt absoluteValue}.  If only the
compiler had warned you!

\index{compile-time error}
\index{error!compile-time}
\index{debugging}

From now on, if the compiler points out an error in your program, you
should not blame the compiler.  Rather, you should thank the compiler
for finding your error and sparing you days of debugging.  Some
compilers have an option that tells them to be extra strict and report
all the errors they can find.  You should turn this option on all the
time.

\index{math function!fabs}

As an aside, you should know that there is a function in the
math library called {\tt fabs} that calculates the absolute
value of a {\tt double}---correctly.

\section{Program development}
\label{distance}
\index{program development}

At this point you should be able to look at complete C++ functions
and tell what they do.  But it may not be clear yet how to go
about writing them.  I am going to suggest one technique that
I call {\bf incremental development}.

\index{incremental development}
\index{program development}

As an example, imagine you want to find the distance between two
points, given by the coordinates $(x_1, y_1)$ and $(x_2, y_2)$.  By
the usual definition,

\begin{equation}
distance = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}
\end{equation}
%
The first step is to consider what a {\tt distance} function
should look like in C++.  In other words, what are the inputs
(parameters) and what is the output (return value).

In this case, the two points are the parameters, and it is natural to
represent them using four {\tt double}s.  The return value is the
distance, which will have type {\tt double}.

Already we can write an outline of the function:

\begin{verbatim}
double distance (double x1, double y1, double x2, double y2) {
  return 0.0;
}
\end{verbatim}
%
The {\tt return} statement is a placekeeper so that the function will
compile and return something, even though it is not the right answer.
At this stage the function doesn't do anything useful, but it is
worthwhile to try compiling it so we can identify any syntax errors
before we make it more complicated.

In order to test the new function, we have to call it with
sample values.  Somewhere in {\tt main} I would add:

\begin{verbatim}
  double dist = distance (1.0, 2.0, 4.0, 6.0);
  cout << dist << endl;
\end{verbatim}
%
I chose these values so that the horizontal
distance is 3 and the vertical distance is 4; that way,
the result will be 5 (the hypotenuse of a 3-4-5 triangle).
When you are testing a function, it is useful to know the right
answer.

Once we have checked the syntax of the function definition, we
can start adding lines of code one at a time.  After each
incremental change, we recompile and run the program.  That
way, at any point we know exactly where the error must be---in
the last line we added.

The next step in the computation is to find the differences
$x_2 - x_1$ and $y_2 - y_1$.  I will store those values in
temporary variables named {\tt dx} and {\tt dy}.

\begin{verbatim}
double distance (double x1, double y1, double x2, double y2) {
  double dx = x2 - x1;
  double dy = y2 - y1;
  cout << "dx is " << dx << endl;
  cout << "dy is " << dy << endl;
  return 0.0;
}
\end{verbatim}
%
I added output statements that will let me check the intermediate
values before proceeding.  As I mentioned, I already know that they
should be 3.0 and 4.0.

\index{scaffolding}

When the function is finished I will remove the output statements.  Code
like that is called {\bf scaffolding}, because it is helpful for
building the program, but it is not part of the final product.
Sometimes it is a good idea to keep the scaffolding around, but
comment it out, just in case you need it later.

The next step in the development is to square {\tt dx} and {\tt dy}.
We could use the {\tt pow} function, but it is simpler and
faster to just multiply each term by itself.

\begin{verbatim}
double distance (double x1, double y1, double x2, double y2) {
  double dx = x2 - x1;
  double dy = y2 - y1;
  double dsquared = dx*dx + dy*dy;
  cout << "dsquared is " << dsquared;
  return 0.0;
}
\end{verbatim}
%
Again, I would compile and run the program at this stage
and check the intermediate value (which should be 25.0).

Finally, we can use the {\tt sqrt} function to compute and
return the result.

\begin{verbatim}
double distance (double x1, double y1, double x2, double y2) {
  double dx = x2 - x1;
  double dy = y2 - y1;
  double dsquared = dx*dx + dy*dy;
  double result = sqrt (dsquared);
  return result;
}
\end{verbatim}
%
Then in {\tt main}, we should output and check the value of the result.

As you gain more experience programming, you might find yourself
writing and debugging more than one line at a time.  Nevertheless,
this incremental development process can save you a lot of
debugging time.

The key aspects of the process are:

\begin{itemize}

\item Start with a working program and make small, incremental
changes.  At any point, if there is an error, you will know
exactly where it is.

\item Use temporary variables to hold intermediate values so
you can output and check them.

\item Once the program is working, you might want to remove
some of the scaffolding or consolidate multiple statements into
compound expressions, but only if it does not make the program
difficult to read.

\end{itemize}

\section{Composition}
\index{composition}

As you should expect by now, once you define a new function,
you can use it as part of an expression, and you can build
new functions using existing functions.  For example, what if someone
gave you two points, the center of the circle and a point on
the perimeter, and asked for the area of the circle?

Let's say the center point is stored in the variables {\tt xc}
and {\tt yc}, and the perimeter point is in {\tt xp} and
{\tt yp}.  The first step is to find the radius of the circle, which
is the distance between the two points.  Fortunately, we have
a function, {\tt distance}, that does that.

\begin{verbatim}
  double radius = distance (xc, yc, xp, yp);
\end{verbatim}
%
The second step is to find the area of a circle with that
radius, and return it.

\begin{verbatim}
  double result = area (radius);
  return result;
\end{verbatim}
%
Wrapping that all up in a function, we get:

\begin{verbatim}
double fred (double xc, double yc, double xp, double yp) {
  double radius = distance (xc, yc, xp, yp);
  double result = area (radius);
  return result;
} 
\end{verbatim}
%
The name of this function is {\tt fred}, which may seem odd.  I will
explain why in the next section.

The temporary variables {\tt radius} and {\tt area} are
useful for development and debugging, but once the program is
working we can make it more concise by composing
the function calls:

\begin{verbatim}
double fred (double xc, double yc, double xp, double yp) {
  return area (distance (xc, yc, xp, yp));
} 
\end{verbatim}

\section{Overloading}
\label{overloading}
\index{overloading}

In the previous section you might have noticed that {\tt fred}
and {\tt area} perform similar functions---finding
the area of a circle---but take different parameters.  For
{\tt area}, we have to provide the radius; for {\tt fred}
we provide two points.

If two functions do the same thing, it is natural to give them
the same name.  In other words, it would make more sense if
{\tt fred} were called {\tt area}.

Having more than one function with the same name, which is called {\bf
overloading}, is legal in C++ {\em as long as each version takes
different parameters}.  So we can go ahead and rename {\tt fred}:

\begin{verbatim}
double area (double xc, double yc, double xp, double yp) {
  return area (distance (xc, yc, xp, yp));
} 
\end{verbatim}
%
This looks like a recursive function, but it is not.  Actually,
this version of {\tt area} is calling the other version.
When you call an overloaded function, C++ knows which version you
want by looking at the arguments that you provide.  If you write:

\begin{verbatim}
    double x = area (3.0);
\end{verbatim}
%
C++ goes looking for a function named {\tt area} that
takes a {\tt double} as an argument, and so it uses the
first version.  If you write

\begin{verbatim}
    double x = area (1.0, 2.0, 4.0, 6.0);
\end{verbatim}
%
C++ uses the second version of {\tt area}.  

Many of the built-in C++ commands are overloaded, meaning that there
are different versions that accept different numbers or types of
parameters.

Although overloading is a useful feature, it should be used with
caution.  You might get yourself nicely confused if you are trying to
debug one version of a function while accidently calling a different
one.

Actually, that reminds me of one of the cardinal rules of debugging:
{\bf make sure that the version of the program you are looking at is
the version of the program that is running!}  Some time you may find
yourself making one change after another in your program, and seeing
the same thing every time you run it.  This is a warning sign that for
one reason or another you are not running the version of the program
you think you are.  To check, stick in an output statement (it
doesn't matter what it says) and make sure the behavior of the
program changes accordingly.

\section{Boolean values}
\index{boolean}
\index{value!boolean}

The types we have seen so far are pretty big.  There are a lot
of integers in the world, and even more floating-point numbers.
By comparison, the set of characters is pretty small.  Well, there
is another type in C++ that is even smaller.  It is called
{\bf boolean}, and the only values in it are
{\tt true} and {\tt false}.

Without thinking about it, we have been using boolean values for the
last couple of chapters.  The condition inside an {\tt if}
statement or a {\tt while} statement is a boolean expression.
Also, the result of a comparison operator is a boolean value.
For example:

\begin{verbatim}
  if (x == 5) {
    // do something
  }
\end{verbatim}
%
The operator {\tt ==} compares two integers and produces a
boolean value.

\index{operator!comparison}
\index{comparison operator}

The values {\tt true} and {\tt false} are keywords in C++,
and can be used anywhere a boolean expression is called for.
For example, 

\begin{verbatim}
  while (true) {
    // loop forever
  }
\end{verbatim}
%
is a standard idiom for a loop that should run forever (or
until it reaches a {\tt return} or {\tt break} statement).

\section{Boolean variables}
\index{type!{\tt bool}}

As usual, for every type of value, there is a corresponding
type of variable.  In C++ the boolean type is called {\bf bool}.
Boolean variables work just like the other types:

\begin{verbatim}
  bool fred;
  fred = true;
  bool testResult = false;
\end{verbatim}
%
The first line is a simple variable declaration;
the second line is an assignment, and the third line is a
combination of a declaration and as assignment, 
called an initialization.

\index{initialization}
\index{statement!initialization}

As I mentioned, the result of a comparison operator is a boolean,
so you can store it in a {\tt bool} variable

\begin{verbatim}
  bool evenFlag = (n%2 == 0);     // true if n is even
  bool positiveFlag = (x > 0);    // true if x is positive
\end{verbatim}
%
and then use it as part of a conditional statement later

\begin{verbatim}
  if (evenFlag) {
    cout << "n was even when I checked it" << endl;
  }
\end{verbatim}
%
A variable used in this way is called a {\bf flag},
since it flags the presence or absence of some condition.

\index{flag}

\section{Logical operators}
\index{logical operator}
\index{operator!logical}

There are three {\bf logical operators} in C++: AND, OR and NOT,
which are denoted by the symbols {\tt \&\&}, {\tt ||} and
{\tt !}.  The semantics (meaning) of these operators is similar
to their meaning in English.  For example {\tt x > 0 \&\& x < 10}
is true only if {\tt x} is greater than zero AND less than 10.

\index{semantics}

{\tt evenFlag || n\%3 == 0} is true if {\em either} of
the conditions is true, that is, if {\tt evenFlag} is true OR the
number is divisible by 3.

Finally, the NOT operator has the effect of negating or
inverting a bool expression, so {\tt !evenFlag} is true
if {\tt evenFlag} is false; that is, if the number is odd.

\index{nested structure}

Logical operators often provide a way to simplify nested
conditional statements.  For example, how would you write
the following code using a single conditional?

\begin{verbatim}
  if (x > 0) {
    if (x < 10) {
      cout << "x is a positive single digit." << endl;
    }
  }
\end{verbatim}

\section{Bool functions}
\label{bool}
\index{bool}
\index{function!bool}

Functions can return {\tt bool} values just like any other type,
which is often convenient for hiding complicated tests inside
functions.  For example:

\begin{verbatim}
bool isSingleDigit (int x)
{
  if (x >= 0 && x < 10) {
    return true;
  } else {
    return false;
  }
}
\end{verbatim}
%
The name of this function is {\tt isSingleDigit}.  It is common
to give boolean functions names that sound like yes/no questions.
The return type is {\tt bool}, which means that every return
statement has to provide a {\tt bool} expression.

The code itself is straightforward, although it is a bit longer than
it needs to be.  Remember that the expression {\tt x >= 0 \&\& x < 10}
has type {\tt bool}, so there is nothing wrong with returning it
directly, and avoiding the {\tt if} statement altogether:

\begin{verbatim}
bool isSingleDigit (int x)
{
  return (x >= 0 && x < 10);
}
\end{verbatim}
%
In {\tt main} you can call this function in the usual ways:

\begin{verbatim}
  cout << isSingleDigit (2) << endl;
  bool bigFlag = !isSingleDigit (17);
\end{verbatim}
%
The first line outputs the value {\tt true} because 2 is a
single-digit number.  Unfortunately, when C++ outputs {\tt bool}s, it
does not display the words {\tt true} and {\tt false}, but rather the
integers {\tt 1} and {\tt 0}.\footnote{There is a way to fix that
using the {\tt boolalpha} flag, but it is too hideous to mention.}

The second line assigns the value {\tt true} to {\tt bigFlag}
only if 17 is {\em not} a single-digit number.

The most common use of {\tt bool} functions is inside conditional
statements

\begin{verbatim}
  if (isSingleDigit (x)) {
    cout << "x is little" << endl;
  } else {
    cout << "x is big" << endl;
  }
\end{verbatim}

\section {Returning from {\tt main}}

Now that we have functions that return values, I can let you in
on a secret.  {\tt main} is not really supposed to be a {\tt void}
function.  It's supposed to return an integer:

\begin{verbatim}
int main ()
{
  return 0;
}  
\end{verbatim}
%
The usual return value from {\tt main} is 0, which indicates that
the program succeeded at whatever it was supposed to to.  If something
goes wrong, it is common to return -1, or some other value that
indicates what kind of error occurred.

Of course, you might wonder who this value gets returned to, since
we never call {\tt main} ourselves.  It turns out that when the
system executes a program, it starts by calling {\tt main}
in pretty much the same way it calls all the other functions.

There are even some parameters that are passed to {\tt main}
by the system, but we are not going to deal with them for a little
while.

\section {More recursion}
\index{recursion}
\index{language!complete}

So far we have only learned a small subset of C++, but you
might be interested to know that this subset is now
a {\bf complete} programming language, by which I
mean that anything that can be computed can be expressed in this
language.  Any program ever written could be rewritten
using only the language features we have used so far (actually, we
would need a few commands to control devices like the keyboard, mouse,
disks, etc., but that's all).

\index{Turing, Alan}

Proving that claim is a non-trivial exercise first
accomplished by Alan Turing, one of the first computer scientists
(well, some would argue that he was a mathematician, but a lot of the
early computer scientists started as mathematicians).  Accordingly, it
is known as the Turing thesis.  If you take a course on the Theory of
Computation, you will have a chance to see the proof.

To give you an idea of what you can do with the tools we have learned
so far, we'll evaluate a few recursively-defined
mathematical functions.  A recursive definition is similar to a
circular definition, in the sense that the definition contains a
reference to the thing being defined.  A truly circular definition is
typically not very useful:

\begin{description}

\item[frabjuous:] an adjective used to describe
something that is frabjuous.

\index{frabjuous}

\end{description}

If you saw that definition in the dictionary, you might be
annoyed.  On the other hand, if you looked up the definition
of the mathematical function {\bf factorial}, you might
get something like:

\begin{eqnarray*}
&&  0! = 1 \\
&&  n! = n \cdot (n-1)!
\end{eqnarray*}

(Factorial is usually denoted with the symbol $!$, which is
not to be confused with the C++ logical operator {\tt !} which
means NOT.)  This definition says that the factorial of 0 is 1,
and the factorial of any other value, $n$, is $n$ multiplied
by the factorial of $n-1$.  So $3!$ is 3 times $2!$, which is 2 times
$1!$, which is 1 times 0!.  Putting it all together, we get
$3!$ equal to 3 times 2 times 1 times 1, which is 6.

If you can write a recursive definition of something, you can usually
write a C++ program to evaluate it.  The first step is to decide what
the parameters are for this function, and what the return type is.
With a little thought, you should conclude that factorial takes an
integer as a parameter and returns an integer:

\begin{verbatim}
int factorial (int n)
{
}
\end{verbatim}
%
If the argument happens to be zero, all we have to do is
return 1:

\begin{verbatim}
int factorial (int n)
{
  if (n == 0) {
    return 1;
  }
}
\end{verbatim}
%
Otherwise, and this is the interesting part, we have to make
a recursive call to find the factorial of $n-1$, and then
multiply it by $n$.

\begin{verbatim}
int factorial (int n)
{
  if (n == 0) {
    return 1;
  } else {
    int recurse = factorial (n-1);
    int result = n * recurse;
    return result;
  }
}
\end{verbatim}
%
If we look at the flow of execution for this program,
it is similar to {\tt nLines} from the previous chapter.
If we call {\tt factorial} with the value 3:

Since 3 is not zero, we take the second branch and calculate
the factorial of $n-1$...

\begin{quote}
Since 2 is not zero, we take the second branch and calculate
the factorial of $n-1$...

\begin{quote}
Since 1 is not zero, we take the second branch and calculate
the factorial of $n-1$...

\begin{quote}
Since 0 {\em is} zero, we take the first branch and return
the value 1 immediately without making any more recursive
calls.

\end{quote}

The return value (1) gets multiplied by {\tt n}, which is 1,
and the result is returned.

\end{quote}

The return value (1) gets multiplied by {\tt n}, which is 2,
and the result is returned.

\end{quote}

\noindent The return value (2) gets multiplied by {\tt n}, which is 3,
and the result, 6, is returned to {\tt main}, or whoever
called {\tt factorial (3)}.

\index{stack}
\index{diagram!state}
\index{diagram!stack}

Here is what the stack diagram looks like for this sequence of
function calls:

\vspace{0.1in}
\centerline{\epsfig{figure=stack3.eps}}
\vspace{0.1in}
%
The return values are shown being passed back up the stack.

Notice that in the last instance of {\tt factorial}, the local
variables {\tt recurse} and {\tt result} do not exist because
when {\tt n=0} the branch that creates them does not execute.

\section{Leap of faith}
\index{leap of faith}

Following the flow of execution is one way to read programs, but as
you saw in the previous section, it can quickly become labarynthine.
An alternative is what I call the ``leap of faith.''  When you come to
a function call, instead of following the flow of execution, you
{\em assume} that the function works correctly and returns the
appropriate value.

In fact, you are already practicing this leap of faith
when you use built-in functions.  When you call {\tt cos}
or {\tt exp}, you don't examine the implementations of 
those functions.  You just assume that they work, because the people
who wrote the built-in libraries were good programmers.

Well, the same is true when you call one of your own functions.
For example, in Section~\ref{bool} we wrote a function called
{\tt isSingleDigit} that determines whether a number is between
0 and 9.  Once we have convinced ourselves that this function
is correct---by testing and examination of the code---we can
use the function without ever looking at the code again.

The same is true of recursive programs.  When you get to the recursive
call, instead of following the flow of execution, you should {\em
assume} that the recursive call works (yields the correct result), and
then ask yourself, ``Assuming that I can find the factorial of $n-1$,
can I compute the factorial of $n$?''  In this case, it is clear that
you can, by multiplying by $n$.

Of course, it is a bit strange to assume that the function works
correctly when you have not even finished writing it, but that's why
it's called a leap of faith!

\section{One more example}
\index{factorial}

In the previous example I used temporary variables to spell out the
steps, and to make the code easier to debug, but I could have saved a
few lines:

\begin{verbatim}
int factorial (int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial (n-1);
  }
}
\end{verbatim}
%
From now on I will tend to use the more concise version, but
I recommend that you use the more explicit version while you
are developing code.   When you have it working, you can
tighten it up, if you are feeling inspired.

After {\tt factorial}, the classic example of a recursively-defined
mathematical function is {\tt fibonacci}, which has the
following definition:

\begin{eqnarray*}
&& fibonacci(0) = 1 \\
&& fibonacci(1) = 1 \\
&& fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);
\end{eqnarray*}
%
Translated into C++, this is

\begin{verbatim}
int fibonacci (int n) {
  if (n == 0 || n == 1) {
    return 1;
  } else {
    return fibonacci (n-1) + fibonacci (n-2);
  }
}
\end{verbatim}
%
If you try to follow the flow of execution here, even for fairly small
values of {\tt n}, your head explodes.  But according to the leap of
faith, if we assume that the two recursive calls (yes, you can make
two recursive calls) work correctly, then it is clear that we get the
right result by adding them together.

\section{Glossary}

\begin{description}

\item[return type:]  The type of value a function returns.

\item[return value:]  The value provided as the result of a function
call.

\item[dead code:]  Part of a program that can never be executed,
often because it appears after a {\tt return} statement.

\item[scaffolding:]  Code that is used during program development
but is not part of the final version.

\item[void:]  A special return type that indicates a void function;
that is, one that does not return a value.

\item[overloading:]  Having more than one function with the same name
but different parameters.  When you call an overloaded function,
C++ knows which version to use by looking at the arguments you
provide.

\item[boolean:]  A value or variable that can take on one of
two states, often called $true$ and $false$.  In C++, boolean
values can be stored in a variable type called {\tt bool}.

\item[flag:]  A variable (usually type {\tt bool}) that records
a condition or status information.

\item[comparison operator:]  An operator that compares two values
and produces a boolean that indicates the relationship between the
operands.

\item[logical operator:]  An operator that combines boolean values
in order to test compound conditions.

\index{return type}
\index{return value}
\index{dead code}
\index{scaffolding}
\index{void}
\index{overloading}
\index{bool}
\index{operator!conditional}
\index{operator!logical}

\end{description}

